#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

class NumberCombine:
    def __init__(self, target_num):
        self.num = target_num
        self.memory = {}            # dp的记忆体, 空间换时间, 递归中已经计算过的子问题做记录

        self.hit_memory_cnt = 0

    def partion_cnt(self):
        return self.partion_cnt_rec(self.num)

    def partion_cnt_rec(self, num):
        # 返回值: 对num进行分割, 全排列情况(1, 1, 2) 和(2, 1, 1) 是两种情况
        if num == 0:
            return 1
        # if num == 1:
        #     return 1

        cnt = self.memory.get(num)
        if cnt is not None:
            self.hit_memory_cnt += 1
            return cnt

        cnt = 0
        for start in range(1, num+1):
            cnt += self.partion_cnt_rec(num - start)

        self.memory[num] = cnt
        return cnt


def test():

    for i in range(10):
        # print(num, cnt)
        n = NumberCombine(i)
        print(n.partion_cnt(), sep=" ", end=" ")
        # assert n.partion_cnt() == cnt


def main():
    print("start main")
    test()


if __name__ == "__main__":
    main()
